package com.wyr.leetcode.step3;

import java.util.*;

public class FindWordsTest {
    /**
     * 212. 单词搜索 II
     * <p>
     * https://leetcode.cn/problems/word-search-ii/description/?envType=problem-list-v2&envId=array
     */

    public static void main(String[] args) {
        char[][] board = {{'a', 'b', 'c', 'e' }, {'x', 'x', 'c', 'd' }, {'x', 'x', 'b', 'a' }};
        String[] strings = new String[]{"abc", "abcd"};
        findWords(board, strings);
    }

    // 已经找到的复合要求的单词
    static Set<String> helpSet = new HashSet<>();
    // 前缀树
    static Trie trie = new Trie();
    // 所有的单词
    static Set<String> allSet = new HashSet<>();

    public static List<String> findWords(char[][] board, String[] words) {
        // 构建前缀树和初始化
        for (String word : words) {
            trie.insert(word);
            allSet.add(word);
        }
        int[][] used = new int[board.length][board[0].length];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, used, i, j, sb);
            }
        }
        return new ArrayList<>(helpSet);
    }

    public static void dfs(char[][] board, int[][] used, int curX, int curY, StringBuilder sb) {
        if (curX < 0 || curX >= board.length || curY < 0 || curY >= board[0].length || used[curX][curY] == 1) {
            return;
        }
        if (sb.length() > 10) return;
        if (trie.prefixNumber(sb.toString()) == 0) {
            return;
        }
        sb.append(board[curX][curY]);
        // 正确的单词，并且还没有加入helpSet
        if (allSet.contains(sb.toString()) && !helpSet.contains(sb.toString())) {
            helpSet.add(sb.toString());
        }
        used[curX][curY] = 1;
        dfs(board, used, curX - 1, curY, sb);// 上
        dfs(board, used, curX + 1, curY, sb);// 下
        dfs(board, used, curX, curY - 1, sb);// 左
        dfs(board, used, curX, curY + 1, sb);// 右
        used[curX][curY] = 0;
        sb.deleteCharAt(sb.length() - 1);
    }

}

class Trie {
    private TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    // 往前缀树中插入
    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray();
        TrieNode node = root; // 辅助变量，首先指向根节点
        node.pass++; // 根节点的pass首先++
        int index = 0;
        for (int i = 0; i < chs.length; i++) { // 遍历字符数组
            index = chs[i] - 'a'; // 由字符确定走哪条路，即找到nexts这个路径数组的下标
            if (node.nexts[index] == null) { // 这条路之前没有人走过
                node.nexts[index] = new TrieNode();
            }
            node = node.nexts[index];// 移动辅助节点
            node.pass++; // 经过的路程++
        }
        node.end++; // 最后结尾的路的end++
    }

    public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }
        char[] chs = pre.toCharArray();
        TrieNode node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.pass;
    }

    public int search(String word) {
        if (word == null) {
            return 0;
        }
        char[] chs = word.toCharArray();
        TrieNode node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }
}

class TrieNode {
    public int pass;
    public int end;
    public TrieNode[] nexts;

    public TrieNode() {
        this.pass = 0;
        this.end = 0;
        this.nexts = new TrieNode[26];
    }
}
